// C5 example
// 2004-11

using System;
using C5;
using SCG = System.Collections.Generic;

namespace SortingPermutation
{
    class MyTest
    {
        public static void Main(String[] args)
        {
            String[] cities = { "Tokyo", "Beijing", "Hangzhou", "Kyoto", "Beijing", "Copenhagen", "Seattle" };
            IList<String> alst = new ArrayList<String>();
            alst.AddAll(cities);
            foreach (int i in MySort.GetPermutation1(alst))
                Console.Write("{0} ", i);
            Console.WriteLine();
            IList<String> llst = new LinkedList<String>();
            llst.AddAll(cities);
            foreach (int i in MySort.GetPermutation2(llst))
                Console.Write("{0} ", i);
            Console.WriteLine();
            Console.WriteLine("The rank of the cities:");
            ArrayList<int> res = MySort.GetPermutation1(MySort.GetPermutation2(llst));
            foreach (int i in res)
                Console.Write("{0} ", i);
            Console.WriteLine();
        }
    }

    class MySort
    {
        // Fast for array lists and similar, but not stable; slow for linked lists

        public static ArrayList<int> GetPermutation1<T>(IList<T> lst)
          where T : IComparable<T>
        {
            ArrayList<int> res = new ArrayList<int>(lst.Count);
            for (int i = 0; i < lst.Count; i++)
                res.Add(i);
            res.Sort(ComparerFactory<int>.CreateComparer((i, j) => lst[i].CompareTo(lst[j])));
            return res;
        }

        // Stable and fairly fast both for array lists and linked lists, 
        // but does copy the collection's items. 

        public static ArrayList<int> GetPermutation2<T>(IList<T> lst)
          where T : IComparable<T>
        {
            int i = 0;
            IList<KeyValuePair<T, int>> zipList =
              lst.Map<KeyValuePair<T, int>>
                  (delegate(T x) { return new KeyValuePair<T, int>(x, i++); });
            zipList.Sort(new KeyValueComparer<T>(lst));
            ArrayList<int> res = new ArrayList<int>(lst.Count);
            foreach (KeyValuePair<T, int> p in zipList)
                res.Add(p.Value);
            return res;
        }

        private class KeyValueComparer<T> : SCG.IComparer<KeyValuePair<T, int>>
          where T : IComparable<T>
        {
            private readonly IList<T> lst;
            public KeyValueComparer(IList<T> lst)
            {
                this.lst = lst;
            }
            public int Compare(KeyValuePair<T, int> p1, KeyValuePair<T, int> p2)
            {
                return p1.Key.CompareTo(p2.Key);
            }
        }
    }
}
